<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html><head>
<title>Write Ahead Log Notes</title>
<style type="text/css">
body {
    margin: auto;
    font-family: Verdana, sans-serif;
    padding: 8px 1%;
}

a { color: #044a64 }
a:visited { color: #734559 }

.logo { position:absolute; margin:3px; }
.tagline {
  float:right;
  text-align:right;
  font-style:italic;
  width:300px;
  margin:12px;
  margin-top:58px;
}

.toolbar {
  text-align: center;
  line-height: 1.6em;
  margin: 0;
  padding: 0px 8px;
}
.toolbar a { color: white; text-decoration: none; padding: 6px 12px; }
.toolbar a:visited { color: white; }
.toolbar a:hover { color: #044a64; background: white; }

.content    { margin: 5%; }
.content dt { font-weight:bold; }
.content dd { margin-bottom: 25px; margin-left:20%; }
.content ul { padding:0px; padding-left: 15px; margin:0px; }

/* rounded corners */
.se  { background: url(images/se.gif) 100% 100% no-repeat #044a64}
.sw  { background: url(images/sw.gif) 0% 100% no-repeat }
.ne  { background: url(images/ne.gif) 100% 0% no-repeat }
.nw  { background: url(images/nw.gif) 0% 0% no-repeat }

/* Things for "fancyformat" documents start here. */
.fancy img+p {font-style:italic}
.fancy .codeblock i { color: darkblue; }
.fancy h1,.fancy h2,.fancy h3,.fancy h4 {font-weight:normal;color:#044a64}
.fancy h2 { margin-left: 10px }
.fancy h3 { margin-left: 20px }
.fancy h4 { margin-left: 30px }
.fancy th {white-space:nowrap;text-align:left;border-bottom:solid 1px #444}
.fancy th, .fancy td {padding: 0.2em 1ex; vertical-align:top}
.fancy #toc a        { color: darkblue ; text-decoration: none }
.fancy .todo         { color: #AA3333 ; font-style : italic }
.fancy .todo:before  { content: 'TODO:' }
.fancy p.todo        { border: solid #AA3333 1px; padding: 1ex }
.fancy img { display:block; }
.fancy :link:hover, .fancy :visited:hover { background: wheat }
.fancy p,.fancy ul,.fancy ol { margin: 1em 5ex }
.fancy li p { margin: 1em 0 }
/* End of "fancyformat" specific rules. */

</style>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
  
</head>
<body>
<div><!-- container div to satisfy validator -->

<a href="index.html">
<img class="logo" src="images/sqlite370_banner.gif" alt="SQLite Logo"
 border="0"></a>
<div><!-- IE hack to prevent disappearing logo--></div>
<div class="tagline">Small. Fast. Reliable.<br>Choose any three.</div>

<table width=100% style="clear:both"><tr><td>
  <div class="se"><div class="sw"><div class="ne"><div class="nw">
  <table width=100% style="padding:0;margin:0;cell-spacing:0"><tr>
  <td width=100%>
  <div class="toolbar">
    <a href="about.html">About</a>
    <a href="sitemap.html">Sitemap</a>
    <a href="docs.html">Documentation</a>
    <a href="download.html">Download</a>
    <a href="copyright.html">License</a>
    <a href="news.html">News</a>
    <a href="support.html">Support</a>
  </div>
<script>
  gMsg = "Search SQLite Docs..."
  function entersearch() {
    var q = document.getElementById("q");
    if( q.value == gMsg ) { q.value = "" }
    q.style.color = "black"
    q.style.fontStyle = "normal"
  }
  function leavesearch() {
    var q = document.getElementById("q");
    if( q.value == "" ) { 
      q.value = gMsg
      q.style.color = "#044a64"
      q.style.fontStyle = "italic"
    }
  }
</script>
<td>
    <div style="padding:0 1em 0px 0;white-space:nowrap">
    <form name=f method="GET" action="http://www.sqlite.org/search">
      <input id=q name=q type=text
       onfocus="entersearch()" onblur="leavesearch()" style="width:24ex;padding:1px 1ex; border:solid white 1px; font-size:0.9em ; font-style:italic;color:#044a64;" value="Search SQLite Docs...">
      <input type=submit value="Go" style="border:solid white 1px;background-color:#044a64;color:white;font-size:0.9em;padding:0 1ex">
    </form>
    </div>
  </table>
</div></div></div></div>
</td></tr></table>
<div class=startsearch></div>
  




    <div class=fancy>
    <div style="font-size:2em;text-align:center;color:#044a64">
      Write Ahead Log Notes
    </div>
    <div style="font-size:1.5em;margin:1em;color:#044a64">
      Table Of Contents</div>
    <div id=toc> <div style="margin-left:6ex"><a href="#section_1">1. Log File Format</a></div><div style="margin-left:12ex"><a href="#section_1_1">1.1. Header Page Detail</a></div><div style="margin-left:12ex"><a href="#section_1_2">1.2. Control Page Detail</a></div><div style="margin-left:6ex"><a href="#section_2">2. Recovering a Log File</a></div><div style="margin-left:6ex"><a href="#section_3">3. Database Write Operations</a></div><div style="margin-left:12ex"><a href="#section_3_1">3.1. Writing a Transaction</a></div><div style="margin-left:12ex"><a href="#section_3_2">3.2. Checkpoint Operations</a></div><div style="margin-left:12ex"><a href="#section_3_3">3.3. Wrapping a Log File</a></div><div style="margin-left:6ex"><a href="#section_4">4. Database Locking and Read Operations</a></div> </div>
    <div class=startsearch></div>
  

<h1 id="section_1">1. Log File Format</h1>

<p>
  A Write Ahead Log (WAL) file is divided into pages in the same way as an
  SQLite database file. Like an SQLite database file, pages are numbered
  starting from 1. The page size of a WAL file is the same as the page size
  of the corresponding database file. There are three types of pages in the
  log file, as follows:

<ul>
  <li> <b>Header page</b>. The first page of the log file is the header page.
  <li> <b>Data pages</b>. Each data page contains the image of a database 
       page, and no other data.
  <li> <b>Control pages</b>. Control pages contain logged data that is not
       stored on data pages (e.g. database page numbers for each data page).
</ul>

<p>
  A write-ahead log consists of a series of zero or more log segments.
  Each log segment consists of a single control page followed by a set of
  data pages. Each data page contains the data for a new version of a page
  within the database image. The control page contains the database page
  numbers corresponding to each data page in the log segment, and various
  checksums used to detect corruption in the log file.

<p>
  The header page always begins at offset 0 of the log file. Following this
  is a special control page - "page two". The page designated "page two"
  is usually stored immediately following the header page (on page 2 of the
  log file). However, if the disk sector size is larger than the log file
  page size, "page two" is stored in the first page of the second sector
  of the log file. This allows both the header page and this first control 
  page to be written to without risking damage to the other in the event of
  a power failure.

<p>
  The contents of the latest version of the database may be found by taking 
  the current contents of the database file and replacing the old versions 
  of pages with the new versions found in each log segment in the log file, 
  in order.

<p>
  When it is read (recovered), a log file is in one of three forms, depending
  on the contents of the header page stored at the start of the file:

<ol>
  <li><p>The first page of the log file is a valid header that indicates that
       the log starts with a control page located immediately following
       (or shortly after, depending on the disk sector size) the header page.

  <li><p> The first page of the log file does not contain a valid header file.
       In this case, the log starts with a control page located immediately
       following (or shortly after) the header page. This is similar to 
       case 1, except that since the page-size and disk-sector size are
       both unknown (the disk sector size when the log file was created may
       be different to the sector size when it is being read) the control 
       page must be located by depending on the checksums and trial and 
       error.

  <li><p> The first page of the log file is a valid header file that indicates
       that the log segments stored in a specified range of the file should
       be processed (read) first, before returning to process the log segment
       that begins with a control page immediately following (or shortly after)
       the header file.
</ol>

<center> <img src="logfile.png"> </center>

<p>
  In all three cases, the end of the log occurs when either the end of the
  file is reached or the checksum values found on a control page fail to
  match the contents of a control page or the data pages that follow it.
  Except, if the log file is in form 3, and a checksum fails while reading
  log segments from within the specified range inside the file, discard all
  information read so far and begin reading from the start of the file
  as in form 1.

<h2 id="section_1_1">1.1. Header Page Detail</h2>
  <table style="margin:1em auto; width:80%; border-spacing:0" border="0"> <tr style="text-align:left"><th>Field <th>Description
    <tr style="text-align:left;background-color:#DDDDDD"><td> Page size
        <td> Size of log pages in bytes.

    <tr style="text-align:left"><td> Page two location
        <td> Location of the physically first control page in the log file.
             This is determined by the disk sector size.

    <tr style="text-align:left;background-color:#DDDDDD"><td> Gap region start
        <td> If the log is arranged within the log file as in form 3 above,
             this field stores the page number of the first page in the
             range of pages from the body of the file to read first. If the
             log file is not in form 3, this field is set to 0.

    <tr style="text-align:left"><td> Gap region end
        <td> If the log is arranged within the log file as in form 3 above,
             this field stores the page number of the last page in the
             range of pages from the body of the file to read first. If the
             log file is not in form 3, this field is set to 0.

    <tr style="text-align:left;background-color:#DDDDDD"><td nowrap="1"> Gap control page checksum
        <td> If the log is arranged within the log file as in form 3 above,
             this field stores a copy of the control page checksum field of
             the first page in the gap region.

    <tr style="text-align:left"><td> Checksum
        <td> Checksum based on the contents of this page (except for the bytes
             occupied by this field).
  </table>

<h2 id="section_1_2">1.2. Control Page Detail</h2>

<table style="margin:1em auto; width:80%; border-spacing:0" border="0"> <tr style="text-align:left"><th>Field <th>Description
    <tr style="text-align:left;background-color:#DDDDDD"><td> Page size
        <td> Size of log pages in bytes. TODO: This is only really
             necessary on the first control page in the file.

    <tr style="text-align:left"><td> Segment id
        <td> Integer value incremented with each log segment written to the
             log file. The purpose of this is currently to make sure that 
             the control page checksum changes even if the data does not.

    <tr style="text-align:left;background-color:#DDDDDD"><td> Next control page
        <td> The page number of the next control page in the log. Specifying
             this explicitly (instead of implicitly based on the number of data
             pages that follow the current control page) allows control pages
             to be aligned to the start of disk sector boundaries.

    <tr style="text-align:left"><td> Commit flag
        <td> A Boolean flag indicating whether or not the log segment headed
             by the control page is a commit record. The last log segment
             written to the log by each SQL transaction is marked as a commit
             record.

    <tr style="text-align:left;background-color:#DDDDDD"><td> Database size
        <td> This field is only used by commit records. The number of pages
             in the database at the conclusion of the transaction.

    <tr style="text-align:left"><td> Data page count
        <td> The number of data pages in the log segment headed by the 
             control page.

    <tr style="text-align:left;background-color:#DDDDDD"><td> First skip page 
        <td> Normally, data pages are stored as a contiguous block immediately
             following the control page. However, occasionally this block is
             interrupted, as in "data 4" in "Log File Form 3" in the diagram
             at the top of this page. In this case, this field is set to the
             page number of the first log page that is part of the block not
             used for data pages associated with this log segment.
                 
    <tr style="text-align:left"><td> Last skip page
        <td> Similar to the "first skip field", except this field contains the
             page number of the last log file page not used as a data page
             associated with this segment.

    <tr style="text-align:left;background-color:#DDDDDD"><td> Master journal pointer
        <td> This field may contain the file name of a master journal file. It
             is only ever used by commit records.

    <tr style="text-align:left"><td> Page Number Array
        <td> A database page number for each data page in the log segment 
             headed by this control page.

    <tr style="text-align:left;background-color:#DDDDDD"><td> Data checksum
        <td> Checksum based on:
          <ul>
            <li> The contents of each of the data pages in the current log segment.
          </ul>

    <tr style="text-align:left"><td nowrap="1"> Control page checksum
        <td> Checksum based on:
          <ul>
            <li> The contents of this control page, except for the bytes consumed
                 by this field, and
            <li> The control page checksum of the previous control page in the log.
          </ul>

    <tr style="text-align:left;background-color:#DDDDDD"><td> Internal checksum
        <td> This field is only used by the "page two" control page. Checksum based 
             on:
          <ul>
            <li> The contents of this control page, except for this field and the
                 control page checksum field (but including the data checksum).
          </ul>
</table>

<h1 id="section_2">2. Recovering a Log File</h1>

  <p>
    This section describes the process of recovering (reading) a log file.

<h1 id="section_3">3. Database Write Operations</h1>

  <h2 id="section_3_1">3.1. Writing a Transaction</h2>

  <h2 id="section_3_2">3.2. Checkpoint Operations</h2>

  <h2 id="section_3_3">3.3. Wrapping a Log File</h2>

  <p>
    The following diagram shows the procedure for safely "wrapping" the log 
    file. This can only be done once one or more log segments from the start
    of the log file have been checkpointed. The following figure depicts the
    procedure.

<center> <img src="logfile_wrap.png"> </center>

  <p>
    If an OS or power failure occurs during step 2 and the header page is
    left in a corrupted state, the log file is left in form 2. Upon recovery,
    all segments are read from the log file starting from the first control
    page in the log file (marked segment "1" in the diagram above).

  <p>
    As shown in step 3 above, once step 2 has completed and the new header 
    page synced to disk, the checkpointed part of the log file is no longer
    a valid part of the log. If recovery is required, after reading log 
    segment 5, the recovery process will return to the start of the log 
    file and attempt to read a log segment. However, attempting to verify
    the control page checksum using the control page checksum of segment
    5 as one of the inputs will fail, signalling the end of the log.

<center> <img src="logfile_jump.png"> </center>

  <p>
    In scenario A above, if the log segments in the gap region have already
    been checkpointed, the log may simply overwrite the old gap region when
    it encounters it. If a recovery is required, then the header page will
    still point to the old gap region. However, when the recovery process
    attempts to read it, the control page checksum will fail, causing the
    recovery to fallback to starting at the start of the log file (segment 6).

  <p>
    In scenario B, the control page for log segment 8 contains the first
    and last pages of the skip region - a region of pages to jump over when
    reading the data pages for log segment 8.
   

<h1 id="section_4">4. Database Locking and Read Operations</h1>

<p>
  Both writers and checkpointers must obtain a lock before performing any
  work, as follows:

  <ul>
    <li> Writers must obtain the database write-lock before writing to the log 
         file. There may only be one writer at any one time.
    <li> Checkpointers must obtain the database checkpoint-lock before writing
         to the database file. There may only be one checkpointer at any one
         time.
  </ul>





